package com.Oct_Twelve;

import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 08.09. 括号
 * 括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
 *
 * 说明：解集不能包含重复的子集。
 *
 * 例如，给出 n = 3，生成结果为：
 *
 * [
 *   "((()))",
 *   "(()())",
 *   "(())()",
 *   "()(())",
 *   "()()()"
 * ]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/bracket-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/12 15:35
 */

public class Solution08_09 {

    List<String> list;

    public List<String> generateParenthesis(int n) {
        list=new ArrayList<>();
        dfs(n,0,"");
        return list;
    }

    void dfs(int left,int right,String s){
        if (left==0&&right==0)
        {
            list.add(s);
            return;
        }
        if (left>0) dfs(left-1,right+1,s+"(");
        if (right>0) dfs(left,right-1,s+")");
    }

    public static void main(String[] args) {
        Solution08_09 solution08_09=new Solution08_09();
        System.out.println(solution08_09.generateParenthesis(3));
    }
}
